package main

func searchInsert(nums []int, target int) int {
	// 寻找左边界
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left >= len(nums) {
		left = len(nums)
	}
	return left
}

func main() {
	nums := []int{1, 3, 5, 6}
	println(searchInsert(nums, 5) == 2)
	println(searchInsert(nums, 2) == 1)
	println(searchInsert(nums, 7) == 4)
}
